package com.fr.lintcode;

import org.junit.Test;

public class Q975 {

	/**
	 * @param n
	 *            : The number of 'A'
	 * @return: the minimum number of steps to get n 'A'
	 */
	public int minSteps(int n) {
		int dp[] = new int[n + 1];
		dp[0] = 0;
		for (int i = 1; i <= n; i++) {
			for(int j = i-1; j>0;j--){
				if(i % j == 0){
					dp[i] =  dp[j] + i /j;
					break;
				}
			}
			
		}                                          
		return dp[n];
	}
	
	@Test
	public void testMinSteps(){
		System.out.println(minSteps(2));
	}
}
